package chapter18;

import java.util.ArrayList;
import java.util.List;

/**
 * B树
 * 定义：
 * 1.每个x的节点又以下属性：
 * * a. x.n当前存储在节点x中的关键字个数
 * * b. x.n个关键字本身x.key[1],x.key[2],x.key[3]...x.key[n](非降序排列)
 * * c. x.leaf 为ture是叶子节点,否则是内部节点
 * 2.每个内部节点的x都包含n+1的指向其他孩子的指针x.c[1],x.c[2],x.c[3]...x.c[n],x.c[n+1],叶节点的x.c为空
 * 3.关键字x.key[i]对存储在各子树中的关键字范围加以分割, x.key[1]<=key[1]<=x.key[2]<=key[2]<=x.key[3]...<=x.key[x.n]<=key[x.n+1]
 * 4.每个叶子节点具有相同的高度,即数的高度h
 * 5.每个节点包含的关键字数量有上界和下届,用[最小度数]的固定整数t>=2来表示：
 * * a.除了根节点意外的每一个节点至少村长t-1个关键字。因此，除了树根以为的节点至少有t个孩子。如果树是非空，则至少村长一个关键字
 * * b.每个节点至多可包含2*t-1个关键字，因此一个内部节点至多包含2*t个孩子。当要给节点正好存在2*t-1个关键字时，说明这个节点是[满]的
 * <p>
 * 节点的孩子数量x: t<=x<=2*t
 * 节点的关键字数量y: t-1<=y<=2*t-1
 * <p>
 * t=2时候的B树是最简单的，每个节点有2/3/4个孩子，则这是一颗234树。
 * <p>
 * t越大，树的高度越小
 */
public class Btree {

    /**
     * 区间查找
     */
    public static TargetNode search(Node x, int k) {
        int i = 0;
        while (i < x.n && k > x.keys.get(i)) {
            i++;
        }
        if (i < x.n && k == x.keys.get(i)) {
            return new TargetNode(x, i);
        } else if (x.leaf) {
            return null;
        } else {
            return search(x.c.get(i), k);
        }
    }

    public static void create(Node T) {
        Node x = new Node(0);
        x.leaf = true;
        T.root = x;
    }

    public static void splitChild(Node x, int i) {
        Node y = x.c.get(i);
        int t = x.t;
        // 构造新节点
        Node z = new Node();
        // 满节点时候是2*t-1个关键字,分裂后减少t
        z.n = t - 1;
        z.leaf = y.leaf;
        // 新节点取走t个关键字,并删除其他节点
        List<Integer> moveKey = new ArrayList<>();
        for (int j = 0; j <= t - 1; j++) {
            int num = y.keys.get(t - 1 + j);
            z.addKey(j, num);
            moveKey.add(num);
        }
        y.keys.removeAll(moveKey);
        // 如果不是叶子节点
        if (!y.leaf) {
            List<Node> moveNode = new ArrayList<>();
            for (int j = 0; j <= t; j++) {
                Node c = y.c.get(t - 1 + j);
                z.addC(j, c);
                moveNode.add(c);
            }
            y.c.removeAll(moveNode);
        }
        // y的节点数剩t-1
        y.n = t - 1;
        // 将父节点x从i开始往后后移,将新节点z插入到i+1处,关键字也同样处理
        for (int j = x.n; j >= i + 1; j--) {
            x.addC(j + 1, x.c.get(j));
        }
        for (int j = x.n - 1; j >= i; j--) {
            x.addKey(j + 1, x.keys.get(j));
        }
        // 提取t位置的作为父节点关键字
        x.addKey(i, z.keys.get(0));
        z.keys.remove(0);
        // 将z插入
        x.addC(i + 1, z);
        x.n++;
    }

    public static void nonFull(Node x, int k) {
        int i = x.n - 1;
        // 如果是叶子节点
        if (x.leaf) {
            // 后移
            while (i >= 0 && k < x.keys.get(i)) {
                x.addKey(i + 1, x.keys.get(i));
                i--;
            }
            // 将k插入到找到的位置
            x.addKey(i + 1, k);
            x.n++;
        } else {
            // 找到插入的位置,这里的插入是子节点插入位置
            while (i >= 0 && k < x.keys.get(i)) {
                i--;
            }
            i++;
            // 如果是满树要根据t分裂
            int t = x.t;
            if (x.c.get(i).n == 2 * t - 1) {
                // 分裂节点
                splitChild(x, i);
                // 如果是满树又因为大于i位置的k,则当前子节点的右边兄弟节点插入
                if (k > x.keys.get(i)) {
                    i++;
                }
            }
            // 如果不是叶子那么一定是中间节点,必然存在向下指针,向下遍历,找到叶子插入
            nonFull(x.c.get(i), k);
        }
    }

    /**
     * 插入就是不断下推,如果下推路线上节点已经满了,代表将要插入的节点也已经满了,需要进行分裂,分出更多的空间给将要插入的关键字
     */
    public static void insert(Node T, int k) {
        Node r = T.root;
        int t = r.t;
        if (r.n == 2 * t - 1) {
            Node s = new Node(0);
            T.root = s;
            s.leaf = false;
            s.addC(0, r);
            splitChild(s, 0);
            nonFull(s, k);
        } else {
            nonFull(r, k);
        }
    }

    /**
     * 有几种情况：
     * 1.如果关键字k在节点x中,x是叶子节点,则从x中删除k
     * 2.如果关键字k在节点x中,x是叶内部节点：
     * * a.如果节点x中前与K的子节点y至少包含t个关键字,则找出k在以y为根的子树中的前驱k`。递归地删除k`，并在x中用k`替换k
     * * b.对称的，如果y有少于t个关键字，则检查节点x中后于k的子节点z。如果z至少包含t个关键字，则找出k在以z为根的子树中的后继k`，并在x中用k`替代k
     * * c.否则，如果y和z都只有t-1个关键字,则将k和z全部合并进y，这样x失去了k和指向z的指针，并且y现在包含2*t-1个关键字。并且释放z并递归的从y删除k
     * 3.如果关键字k当前不在内部节点x中，则确定必包含k的子树根x.c[i]，如果x.[i]只有t-1个关键字,必须执行3a或3b来保证降至一个至少包含t个关键字的节点。然后，通过对x的某个合适的子节点进行递归而结束。
     * * a.如果x.c[i]只有t-1个关键字，但是他的一个相邻的兄弟至少包含t个关键字，则将x中的某一个关键字下降至x.c[i]中，将x.c[i]相邻的左兄弟或者右兄弟的一个关键字上升至x，将该兄弟中相应的孩子指针移动x.c[i]中，这样使得x.c[i]增加了一个关键字
     * * b.如果x.c[i]和x.c[i]的相邻的兄弟都是只包含t-1个关键字，则将x.c[i]与一个兄弟合并，即将一个关键字移动到新合并的节点，使之成为该节点的中间关键字
     * <p>
     * 简单来说，删除过程中主要会破坏性质5，不管是合并节点或者拆分节点，都是为了保持B树的性质
     * <p>
     * O(th)=O(t*log_t(n))
     */
    public static void delete(Node x, int k) {
        int i = 0;
        for (; i < x.n; i++) {
            if (x.keys.get(i) >= k) {
                break;
            }
        }
        // 如果是叶子就直接删除
        if (i < x.n && x.keys.get(i) == k) {
            // 情况1
            if (x.leaf) {
                x.keys.remove(i);
                x.n--;
            } else {
                Node y = x.c.get(i);
                // 情况2.a
                if (y.n >= x.t) {
                    // 前驱
                    Node y1 = y;
                    while (!y1.leaf) {
                        y1 = y1.c.get(y1.n + 1);
                    }
                    int y1k = y1.keys.get(y1.n);
                    delete(y, y1k);
                    x.addKey(i, y1k);
                } else {
                    Node z = x.c.get(i + 1);
                    // 情况2.b
                    if (z.n >= x.t) {
                        // 后继
                        Node z1 = z;
                        while (!z1.leaf) {
                            z1 = z1.c.get(0);
                        }
                        int z1k = z1.keys.get(0);
                        delete(y, z1k);
                        x.addKey(i, z1k);
                    } else {
                        // 情况2.c
                        if (y.n == x.t - 1 && z.n == x.t - 1) {
                            y.keys.add(k);
                            y.keys.addAll(z.keys);
                            y.c.addAll(z.c);
                            y.n = 2 * x.t - 1;
                            x.keys.remove(i);
                            x.c.remove(z);
                            x.n--;
                            if (x == x.root) {
                                x.root = y;
                            }
                            delete(y, k);
                        }
                    }
                }
                delete(y, k);
            }
        } else {
            if (x.leaf) {
                return;
            }
            Node y = x.c.get(i);
            if (i < x.n && y.n == x.t - 1) {
                // 情况3.a
                if (i + 1 <= x.n && x.c.get(i + 1).n >= x.t) {
                    // x一个关键字下降
                    int j = 0;
                    while (j < y.n && x.keys.get(i) < y.keys.get(j)) {
                        j++;
                    }
                    int tj = j + 1;
                    while (j < y.n) {
                        y.addKey(j + 1, y.keys.get(j));
                        j++;
                    }
                    y.addKey(tj, x.keys.get(i));
                    y.n++;
                    x.keys.remove(i);
                    x.n--;

                    // c.get(i + 1)的关键字上升
                    int n = 0;
                    while (n < x.n && x.c.get(i + 1).keys.get(0) < x.keys.get(n)) {
                        n++;
                    }
                    int tn = n + 1;
                    while (n < x.n) {
                        x.addKey(n + 1, x.keys.get(n));
                        n++;
                    }
                    x.addKey(tn, x.c.get(i + 1).keys.get(0));
                    x.c.add(x.c.get(i + 1).c.get(0));
                    x.n++;
                    x.c.get(i + 1).keys.remove(0);
                    x.c.get(i + 1).n--;
                } else if (i - 1 >= 0 && x.c.get(i - 1).n >= x.t) {
                    // x一个关键字下降
                    int j = 0;
                    while (j < y.n && x.keys.get(i) < y.keys.get(j)) {
                        j++;
                    }
                    int tj = j + 1;
                    while (j < y.n) {
                        y.addKey(j + 1, y.keys.get(j));
                        j++;
                    }
                    y.addKey(tj, x.keys.get(i));
                    y.n++;
                    x.keys.remove(i);
                    x.n--;

                    // x.c.get(i - 1)的关键字上升
                    int n = 0;
                    while (n < x.n && x.c.get(i - 1).keys.get(0) < x.keys.get(n)) {
                        n++;
                    }
                    int tn = n + 1;
                    while (n < x.n) {
                        x.addKey(n + 1, x.keys.get(n));
                        n++;
                    }
                    x.addKey(tn, x.c.get(i - 1).keys.get(0));
                    x.c.add(x.c.get(i - 1).c.get(0));
                    x.n++;
                    x.c.get(i - 1).keys.remove(0);
                    x.c.get(i - 1).n--;
                } else {
                    // 情况3.b
                    if (i - 1 >= 0 && x.c.get(i - 1).n == x.t - 1) {
                        int j = 0;
                        while (j < x.c.get(i - 1).n && x.keys.get(i) < x.c.get(i - 1).keys.get(j)) {
                            j++;
                        }
                        int tj = j + 1;
                        while (j < x.c.get(i - 1).n) {
                            x.c.get(i - 1).addKey(j + 1, x.c.get(i - 1).keys.get(j));
                            j++;
                        }
                        x.c.get(i - 1).addKey(tj, x.keys.get(i));
                        x.c.get(i - 1).keys.addAll(y.keys);
                        x.c.get(i - 1).c.addAll(y.c);
                        x.keys.remove(i);
                        x.c.remove(y);
                        x.n--;

                        if (x == x.root) {
                            x.root = y;
                        }
                    } else if (x.c.get(i + 1).n == x.t - 1) {
                        int j = 0;
                        while (j < x.c.get(i + 1).n && x.keys.get(i) < x.c.get(i + 1).keys.get(j)) {
                            j++;
                        }
                        int tj = j + 1;
                        while (j < x.c.get(i + 1).n) {
                            x.c.get(i + 1).addKey(j + 1, x.c.get(i + 1).keys.get(j));
                            j++;
                        }
                        x.c.get(i + 1).addKey(tj, x.keys.get(i));

                        List<Integer> keys = new ArrayList<>(y.keys);
                        keys.addAll(x.c.get(i + 1).keys);
                        x.c.get(i + 1).keys = keys;
                        List<Node> c = new ArrayList<>(y.c);
                        c.addAll(x.c.get(i + 1).c);
                        x.c.get(i + 1).c = c;
                        x.keys.remove(i);
                        x.c.remove(y);
                        x.n--;

                        if (x == x.root) {
                            x.root = y;
                        }
                    }
                }
            }
            delete(y, k);
        }
    }
}
